class Solution
{
public:
    vector<int> stringIndices(vector<string> &wordsContainer, vector<string> &wordsQuery)
    {
        struct TrieNode
        {
            vector<int> indices;
            vector<TrieNode *> children;
            TrieNode() : children(26, nullptr) {}
            ~TrieNode()
            {
                for (TrieNode *child : children)
                {
                    delete child;
                }
            }
        };

        TrieNode *root = new TrieNode();
        for (int i = 0; i < wordsContainer.size(); ++i)
        {
            TrieNode *node = root;
            for (auto it = wordsContainer[i].rbegin(); it != wordsContainer[i].rend(); ++it)
            {
                char c = *it;
                if (node->children[c - 'a'] == nullptr)
                {
                    node->children[c - 'a'] = new TrieNode();
                }
                node = node->children[c - 'a'];
                node->indices.push_back(i);
            }
        }

        unordered_map<TrieNode *, int> cache;
        int minLenIndex = INT_MAX;
        int minLen = INT_MAX;
        for (int i = 0; i < wordsContainer.size(); ++i)
        {
            if (wordsContainer[i].size() < minLen)
            {
                minLen = wordsContainer[i].size();
                minLenIndex = i;
            }
        }
        cache[root] = minLenIndex;

        vector<int> result;
        for (int i = 0; i < wordsQuery.size(); ++i)
        {
            TrieNode *node = root;
            for (auto it = wordsQuery[i].rbegin(); it != wordsQuery[i].rend(); ++it)
            {
                char c = *it;
                if (node->children[c - 'a'] == nullptr)
                {
                    break;
                }
                node = node->children[c - 'a'];
            }
            if (cache.count(node))
            {
                result.push_back(cache[node]);
                continue;
            }
            int minLenIndex = INT_MAX;
            int minLen = INT_MAX;
            for (int index : node->indices)
            {
                if (wordsContainer[index].size() < minLen)
                {
                    minLen = wordsContainer[index].size();
                    minLenIndex = index;
                }
            }
            cache[node] = minLenIndex;
            result.push_back(minLenIndex);
        }
        delete root;
        return result;
    }
};